Automata theory: deterministic and non-deterministic automata and conversions. Grammars: context free grammars, languages for grammars and Parse trees. Turing machines and abstractions of RAM. Decidability, reducibility P and PN classes. Time and spare complexity. NP completeness. -- Course Website
Prerequisites: 1922 (v.8)<br/> Data Structures and Algorithms 120<br/> <br/> or any previous version<br/> <br/> <br/><br/> <br/> AND<br/><br/> <br/> 12333 (v.6)<br/> Design and Analysis of Algorithms 300<br/> <br/> or any previous version